package com.hardy.leetcode;

import java.util.ArrayList;

/**
 *
 Given a string s, partition s such that every substring of the partition is a palindrome.
 Return all possible palindrome partitioning of s.
 For example, given s ="aab",
 Return
 [
   ["aa","b"],
   ["a","a","b"]
 ]
 * User: Ruijie Date: 2016/9/2
 */
public class PalindromePartitioning {
    public static ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res=new ArrayList<ArrayList<String>>();
        if(s.length()==0){
            return res;
        }
        _partition(s,0,"",res);
        return res;
    }

    private static void _partition(String s, int start, String str, ArrayList<ArrayList<String>> res) {
        if(start>=s.length()){
            String[] arrStr=str.split(",");
            ArrayList<String> al=new ArrayList<String>();
            for(String s1:arrStr){
                al.add(s1);
            }
            res.add(al);
            return;
        }
        for(int i=start;i<s.length();i++){
            String subStr=s.substring(start,i+1);
            if(isHuiWen(s,start,i)){
                String newStr;
                if(str.length()>0){
                    newStr=str+","+subStr;
                }else{
                    newStr=subStr;
                }
                _partition(s,i+1,newStr,res);
            }
        }
    }

    private static boolean isHuiWen(String s, int start, int end) {
        if(s.length()==0||s.equals("")||start<0||start>end||end>s.length()){
            return false;
        }
        if(start==end){
            return true;
        }
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;
            }else{
                start++;
                end--;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s="aab";
        System.out.println(partition(s));
    }
}
